package graph.day15;

public class Leetcode_112 {

    boolean flag = false;

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        dfs(0, root, targetSum);
        return flag;
    }

    public void dfs(int sum, TreeNode root, int targetSum) {
        if (root.left == null && root.right == null) {
            if (sum + root.val == targetSum) {
                flag = true;
            }
            return;
        }

        sum += root.val;
        if (root.left != null) dfs(sum, root.left, targetSum);
        if (root.right != null) dfs(sum, root.right, targetSum);
        sum -= root.val;
    }
}
